import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem =new int[10];
    }
    public void iniElem(int[] array){
        for(int i=0;i<array.length;i++){
            elem[i]=array[i];
            usedSize++;
        }
    }
    public void createHeap(){
        // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
        for(int parent=(usedSize-1-1)/2;parent>=0;parent--){
            shiftDown(parent,usedSize);
        }
    }

    public void heapSort(){
        int end=usedSize-1;
        while (end>0){
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }
    }

    public void swap(int[] elem,int start,int end){
        int tmp=elem[start];
        elem[start]=elem[end];
        elem[end]=tmp;

    }

    //parent是调整开始的位置   判断usedsize是结束的位置
    public void shiftDown(int parent,int usedSize){
        int child=parent*2+1;
        while(child<usedSize){
            // 如果右孩子存在，找到左右孩子中较大的孩子,用child进行标记
            if(child+1<usedSize&&elem[child]<elem[child+1]){
               child++;
            }
            if(elem[parent]<elem[child]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
            }else {
                break;//如果孩子都比父母小
            }
            parent=child;
            child=2*parent+1;
        }
    }
    public boolean isFull(){
        if(elem.length>usedSize){
            return false;
        }else {
            return true;
        }
    }

    public void push(int val){
        //将结点插在最后，再向上调整建堆
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        shiftUp(usedSize);
        usedSize++;
    }
    public void shiftUp(int child) {
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[parent]<elem[child]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isEmpty(){
        return usedSize==0;
    }

    public int poll( ) {
        if(isEmpty()){
            return -1;
        }
        int val=elem[0];
        swap(elem,0,usedSize-1);
        shiftDown(0,usedSize-1);
        usedSize--;
        return val;


    }




}
